// scaup
// (c) 2010, Normen Müller, normen.mueller@gmail.com
// $Id: EquivSpec.scala 143 2010-09-26 15:30:47Z normen.mueller $
package scaup.math

/** An element of an equivalence specification.
 *  
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M\u00FCller</a>
 */ 
abstract class EquivElem {
  val id: Symbol

  val annotations: Set[Symbol]

  val constituents: Set[Ident]
}

/** An equivalence specification.
 * 
 *  <p>
 *  <i>Note:</i> The specification fragment <code>element e1 { constituents { ordered { a }, limit { a, b } } }</code> is a legal EQ sentence. The
 *  parser creates two 'a constituents, though! Should the EQ parser take care of this issue or the equivalence specification? The same holds for
 *  <code>absent</code>. These ambiguities are resolved by the respective getter methods, like <code>reqOrdConst</code>.
 *  </p>
 *  
 *  <p>
 *  For further information please refer to:<br/>
 *  Normen Müller, <a href="http://kwarc.info/nmueller/papers/nrmphd.pdf">Change Management on Semi-Structured Documents</a>, PhD thesis,<br/>
 *  School of Engineering & Science, Jacobs University Bremen, Campus Ring 1, 28759 Bremen.
 *  </p>
 *  
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M\u00FCller</a>
 */ 
class EquivSpec(val name: Symbol, private val m: Map[Symbol, Specification] = Map.empty) {
  /** Retrieves the specification which is associated with the given element.
   *
   *  @param e the element for which to retrieve a specification.
   *  @return  the specificatoin associated with the given element, or throws a <code>NoSuchElementException</code>.
   */ 
  def apply(e: EquivElem): EquivCondition = ((s: Specification) => EquivCondition(e, s))(m(e.id))

  /** Optionally returns the specification associated with an element.
   *
   *  @param e the element for which to retrieve a specification.
   *  @return  an option value containing the specification associated with the element, or None if none exists.
   */
  def get(e: EquivElem): Option[EquivCondition] = (m get e.id) match {
    case Some(s) => Some(EquivCondition(e, s))
    case _       => None
  }

  /** The sets of global limit constituents.
   *
   *  <p>Note that here <code>_</code> denotes all elements within the equivalence specification.</p>
   * 
   * @return a set of global limit constituents.
   */
  lazy val glbLimits: Set[Ident] = (m get '⟙) match {
    case Some(Top(Alternative(_, cs) :: Nil)) => (cs find (_.isInstanceOf[AllConstituent])) match {
      case Some(all: AllConstituent) => (((cs - all) map (_.id)) ++ ((elements - '⟙) map (ID(_)))) filterNot (all.but contains)
      case _ => cs map (_.id)
    }
    case _ => Set.empty
  }

  /** The set of specified elements.
   */
  lazy val elements = m.keys.toSet
  
  override def hashCode = name.hashCode + m.hashCode
  
  override def equals(other: Any) = other match {
    case that: EquivSpec => (this eq that) || ((that canEqual this) && this.name == that.name && this.m == that.m)
    case _               => false
  }
  
  def canEqual(other: Any) = other.isInstanceOf[EquivSpec]
}

/** An equivalence condition.
 *
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M\u00FCller</a>
 */
case class EquivCondition(element: EquivElem, specification: Specification) {
  /** The list of sets of required annotations.
   * 
   * @param  e the element for which the list of sets of required annotations to be calculated.
   * @return   a list of sets of required annotations.
   */
  lazy val reqAnnos: List[Set[Symbol]] = (specification.alternatives map (alternative => ((resolved: Set[AbstractAnnotation]) => {
    val (req, rst) = resolved partition (_.isInstanceOf[Required])
    req collect {case r if !(rst exists (a => a.id == r.id && (a.isInstanceOf[Optional] || a.isInstanceOf[Absent]))) => r.id}
  })(resolveAllAnnotation(alternative.annotations)))) match {
    case l if l forall (_ == Set.empty) => Nil
    case l                              => l
  }

  /** The list of sets of optional annotations.
   * 
   * @param  e the element for which the list of sets of optional annotations to be calculated.
   * @return   a list of sets of optional annotations.
   */
  lazy val optAnnos: List[Set[Symbol]] = (specification.alternatives map (alternative => ((resolved: Set[AbstractAnnotation]) => {
    val (req, rst) = resolved partition (_.isInstanceOf[Optional])
    req collect {case r if !(rst exists (a => a.id == r.id && (a.isInstanceOf[Required] || a.isInstanceOf[Absent]))) => r.id}
  })(resolveAllAnnotation(alternative.annotations)))) match {
    case l if l forall (_ == Set.empty) => Nil
    case l                              => l
  }

  /** The list of sets of absent annotations.
   * 
   * @param  e the element for which the list of sets of absent annotations to be calculated.
   * @return   a list of sets of absent annotations.
   */
  lazy val absAnnos: List[Set[Symbol]] = (specification.alternatives map (alternative => ((resolved: Set[AbstractAnnotation]) => {
    val (req, rst) = resolved partition (_.isInstanceOf[Absent])
    req collect {case r if !(rst exists (a => a.id == r.id && (a.isInstanceOf[Required] || a.isInstanceOf[Optional]))) => r.id}
  })(resolveAllAnnotation(alternative.annotations)))) match {
    case l if l forall (_ == Set.empty) => Nil
    case l                              => l
  }

  private def resolveAllAnnotation(as: Set[AbstractAnnotation]): Set[AbstractAnnotation] = (as find (_.isInstanceOf[AllAnnotation])) match {
    case Some(all: AllAnnotation) =>
      val (req, rst) = (as - all) partition (_.isInstanceOf[Required])
      ((req ++ (element.annotations map (new Annotation(_) with Required))) filterNot (all.but contains _.id)) ++ rst
    case _ =>
      as
  }

  /** The list of sets of required and ordered constituents.
   * 
   * @param  e the element for which the list of sets of required and ordered constituents to be calculated.
   * @return   a list of sets of required and ordered constituents.
   */
  lazy val reqOrdConsts: List[Set[Ident]] = (specification.alternatives map (alternative => ((resolved: Set[AbstractConstituent]) => {
    val (req, rst) = resolved partition (c => c.isInstanceOf[Ordered] && c.isInstanceOf[Required])
    req collect {case r if !(rst exists (c => c.id == r.id && (c.isInstanceOf[Unordered] || c.isInstanceOf[Optional] || c.isInstanceOf[Absent]))) => r.id}
  })(resolveAllConstituent(alternative.constituents)))) match {
    case l if l forall (_ == Set.empty) => Nil
    case l                              => l
  }

  /** The list of sets of optional and ordered constituents.
   * 
   * @param  e the element for which the list of sets of optional and ordered constituents to be calculated.
   * @return   a list of sets of optional and ordered constituents.
   */
  lazy val optOrdConsts: List[Set[Ident]] = (specification.alternatives map (alternative => ((resolved: Set[AbstractConstituent]) => {
    val (req, rst) = resolved partition (c => c.isInstanceOf[Ordered] && c.isInstanceOf[Optional])
    req collect {case r if !(rst exists (c => c.id == r.id && (c.isInstanceOf[Unordered] || c.isInstanceOf[Required] || c.isInstanceOf[Absent]))) => r.id}
  })(resolveAllConstituent(alternative.constituents)))) match {
    case l if l forall (_ == Set.empty) => Nil
    case l                              => l
  }

  /** The list of sets of required and unordered constituents.
   * 
   * @param  e the element for which the list of sets of required and unordered constituents to be calculated.
   * @return   a list of sets of required and unordered constituents.
   */
  lazy val reqUOrdConsts: List[Set[Ident]] = (specification.alternatives map (alternative => ((resolved: Set[AbstractConstituent]) => {
    val (req, rst) = resolved partition (c => c.isInstanceOf[Unordered] && c.isInstanceOf[Required])
    req collect {case r if !(rst exists (c => c.id == r.id && (c.isInstanceOf[Ordered] || c.isInstanceOf[Optional] || c.isInstanceOf[Absent]))) => r.id}
  })(resolveAllConstituent(alternative.constituents)))) match {
    case l if l forall (_ == Set.empty) => Nil
    case l                              => l
  }

  /** The list of sets of optional and unordered constituents.
   * 
   * @param  e the element for which the list of sets of optional and unordered constituents to be calculated.
   * @return   a list of sets of optional and unordered constituents.
   */
  lazy val optUOrdConsts: List[Set[Ident]] = (specification.alternatives map (alternative => ((resolved: Set[AbstractConstituent]) => {
    val (req, rst) = resolved partition (c => c.isInstanceOf[Unordered] && c.isInstanceOf[Optional])
    req collect {case r if !(rst exists (c => c.id == r.id && (c.isInstanceOf[Ordered] || c.isInstanceOf[Required] || c.isInstanceOf[Absent]))) => r.id}
  })(resolveAllConstituent(alternative.constituents)))) match {
    case l if l forall (_ == Set.empty) => Nil
    case l                              => l
  }

  /** The list of sets of absent constituents.
   * 
   * @param  e the element for which the list of sets of absent constituents to be calculated.
   * @return   a list of sets of absent constituents.
   */
  lazy val absConsts: List[Set[Ident]] = (specification.alternatives map (alternative => ((resolved: Set[AbstractConstituent]) => {
    val (req, rst) = resolved partition (_.isInstanceOf[Absent])
    req collect {case r if !(rst exists (c => c.id == r.id && (c.isInstanceOf[Required] || c.isInstanceOf[Optional]))) => r.id}
  })(resolveAllConstituent(alternative.constituents)))) match {
    case l if l forall (_ == Set.empty) => Nil
    case l                              => l
  }

  /** The list of sets of local limit constituents.
   * 
   * @param  e the element for which the list of sets of local limit constituents to be calculated.
   * @return   a list of sets of local limit constituents.
   */
  lazy val locLimits: List[Set[Ident]] = (specification.alternatives map (alternative => ((resolved: Set[AbstractConstituent]) => {
    resolved filter (_.isInstanceOf[Limit]) map (_.id)
  })(resolveAllConstituent(alternative.constituents)))) match {
    case l if l forall (_ == Set.empty) => Nil
    case l                              => l
  }

  private def resolveAllConstituent(cs: Set[AbstractConstituent]): Set[AbstractConstituent] =
    Function.tupled(((all: Set[AbstractConstituent], rst: Set[AbstractConstituent]) =>
      all.flatMap[AbstractConstituent, Set[AbstractConstituent]](all => (all: @unchecked) match {
        case all: AllConstituent => all match {
          case _: Ordered => (element.constituents map {
            case id: ID => new Constituent(id) with Required with Ordered
            case id: TupleID => new TupleConstituent(id) with Required with Ordered
          }) filterNot (all.but contains _.id)
          case _: Unordered => (element.constituents map {
            case id: ID => new Constituent(id) with Required with Unordered
            case id: TupleID => new TupleConstituent(id) with Required with Unordered
          }) filterNot (all.but contains _.id)
        }
      }) ++ rst))(cs partition (_.isInstanceOf[AllConstituent]))
}

/** This object provides a simple interface to the equivalence specification parser class.
 * 
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M\u00FCller</a>
 */
object Parser extends Parser {
  import java.text.MessageFormat.{ format }

  def parse(input: String) = phrase(equivspec)(new lexical.Scanner(input)) match {
    case Success(result, _) => result
    case n@_                => error(format("EQ parsing error in\n{0}\n\n", input) + n)
  }
}

// AST ----------------------------------------------------------------------------------

private [math] trait Required
private [math] trait Optional
private [math] trait Absent
private [math] trait Limit
private [math] trait Ordered
private [math] trait Unordered

private [math] sealed abstract class Specification {
  val id: Symbol

  val alternatives: List[Alternative]
  
  def +(other: List[Alternative]): Specification
  
  override def hashCode = id.hashCode + alternatives.hashCode
  
  override def equals(other: Any) = other match {
    case that: Specification => (this eq that) || ((that canEqual this) && this.id == that.id && this.alternatives == that.alternatives)
    case _                   => false
  }
  
  def canEqual(other: Any) = other.isInstanceOf[Specification]
}

private [math] final case class Top(alternatives: List[Alternative] = List(new Alternative)) extends Specification {
  val id: Symbol = '⟙
  
  def +(other: List[Alternative]): Top = Top(alternatives ::: other)
  
  override def canEqual(other: Any) = other.isInstanceOf[Top]
}

private [math] final case class Elm(id: Symbol, val alternatives: List[Alternative] = List(new Alternative)) extends Specification {
  def +(other: List[Alternative]): Elm = Elm(id, alternatives ::: other)
  
  override def canEqual(other: Any) = other.isInstanceOf[Elm]
}

private [math] final case class Alternative(annotations: Set[AbstractAnnotation] = Set.empty, constituents: Set[AbstractConstituent] = Set.empty) {
  override def hashCode = annotations.hashCode + constituents.hashCode
  
  override def equals(other: Any) = other match {
    case that: Alternative => (this eq that) || ((that canEqual this) && this.annotations == that.annotations && this.constituents == that.constituents)
    case _                 => false
  }
  
  def canEqual(other: Any) = other.isInstanceOf[Alternative]
}

private [math] sealed abstract class AbstractAnnotation {
  val id: Symbol
  
  override def hashCode = id.hashCode
  
  override def equals(other: Any) = other match {
    case that: AbstractAnnotation => (this eq that) || ((that canEqual this) && this.interfaces == that.interfaces && this.id == that.id)
    case _                        => false
  }
  
  def canEqual(other: Any) = other.isInstanceOf[AbstractAnnotation]
  
  protected def interfaces = getClass.getInterfaces.toSet
}

private [math] case class Annotation(id: Symbol) extends AbstractAnnotation {
  override def canEqual(other: Any) = other.isInstanceOf[Annotation]
}

private [math] case class AllAnnotation(but: Set[Symbol] = Set.empty) extends AbstractAnnotation {
  val id: Symbol = '∀

  override def hashCode = 41 * super.hashCode + but.hashCode
  
  override def equals(other: Any) = other match {
    case that: AllAnnotation => super.equals(that) && this.but == that.but
    case _                   => false
  }
  
  override def canEqual(other: Any) = other.isInstanceOf[AllAnnotation] 
}

private [math] abstract class Ident {
  type T

  val id: T
}

private [math] case class ID(id: Symbol) extends Ident { type T = Symbol }

private [math] case class TupleID(id: List[Ident]) extends Ident { type T = List[Ident] }

private [math] sealed abstract class AbstractConstituent {
  val id: Ident
  
  override def hashCode = id.hashCode
  
  override def equals(other: Any) = other match {
    case that: AbstractConstituent => (this eq that) || ((that canEqual this) && this.interfaces == that.interfaces && this.id == that.id)
    case _                         => false
  }
  
  def canEqual(other: Any) = other.isInstanceOf[AbstractConstituent]
  
  protected def interfaces = getClass.getInterfaces.toSet
}

private [math] case class Constituent(id: ID) extends AbstractConstituent {
  override def canEqual(other: Any) = other.isInstanceOf[Constituent]  
}

private [math] case class TupleConstituent(id: TupleID) extends AbstractConstituent {
  override def canEqual(other: Any) = other.isInstanceOf[TupleConstituent]
}

private [math] case class AllConstituent(but: Set[Ident] = Set.empty) extends AbstractConstituent {
  val id = ID('∀)

  override def hashCode = 41 * super.hashCode + but.hashCode
  
  override def equals(other: Any) = other match {
    case that: AllConstituent => super.equals(that) && this.but == that.but
    case _                    => false
  }
  
  override def canEqual(other: Any) = other.isInstanceOf[AllConstituent]
}  

private [math] case class TextConstituent() extends AbstractConstituent {
  val id = ID(Symbol("<TEXT>"))
  
  override def canEqual(other: Any) = other.isInstanceOf[TextConstituent]
}

// GRAMMAR ----------------------------------------------------------------------------------=======

import scala.util.parsing.combinator._
import scala.util.parsing.combinator.syntactical._

/* An equivalence specification parser.
 * 
 *  <p>Thanks go to
 *  <ul>
 *   <li>Serge Autexier regarding his fundamental discussions on the EQ syntax.</li>
 *   <li>Marc Wagner regarding his "limit" idea published in <code>M. Wagner. Change-Oriented Architecture for Mathematical Authoring Assistance. PhD thesis, FR Informatik, Universitaet des Saarlandes, 2010.</code></li>
 *  </ul>
 *  </p>
 * 
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M\u00FCller</a>
 */
private [math] class Parser extends StdTokenParsers with ImplicitConversions {
  type Tokens = Lexer
  val lexical: Tokens = new Lexer

  lexical.reserved ++= List("?", "_", "\\", "<TEXT>", "alternatives", "annotations", "absent", "constituents", "equivspec", "extends", "element", "limit", "ordered", "unordered")
  lexical.delimiters ++= List("{", "}", "(", ")", ",")

  lazy val equivspec: Parser[EquivSpec] = ("equivspec" ~> name) ~ opt(`extends`) ~ ("{" ~> rep(element | glblmt) <~ "}") ^^ {
    case name ~ Some(upper) ~ specs => error("'extends' not yet supported")
    case name ~ None ~ specs        => new EquivSpec(name, (Map.empty[Symbol,Specification] /: specs)((m,s) => s match {      
      case t: Top     => (m get '⟙) match {
        case Some(t) => m + {('⟙, m('⟙) + adjust(t.alternatives))}
        case None    => m + {('⟙, t.copy(adjust(t.alternatives)))}
      }        
      case e: Elm => (m get e.id) match {
        case Some(e) => m + {(e.id, m(e.id) + adjust(e.alternatives))}
        case None    => m + {(e.id, e.copy(e.id, adjust(e.alternatives)))}
      }
      case _ => m
    }))
  }

  def adjust(l: List[Alternative]): List[Alternative] = l match {
    case h :: t => adjust(h) :: adjust(t)
    case Nil    => l
  }

  def adjust(a: Alternative): Alternative = Alternative(
    (Set[AbstractAnnotation]() /: a.annotations)((s, a) => a match {
      case (n: AllAnnotation) => (s find (_.id == '∀)) match {
        case Some(o: AllAnnotation) => (s - o) + (new AllAnnotation(o.but ++ n.but) with Required)
        case _ => s + n
      }
      case x => s + x
    }), 
    (Set[AbstractConstituent]() /: a.constituents)((s, c) => c match {
      case (n: AllConstituent) => n match {
        case (_: Ordered) => (s find (x => x.id == ID('∀) && x.isInstanceOf[Ordered])) match {
          case Some(o: AllConstituent) => (s - o) + (new AllConstituent(o.but ++ n.but) with Required with Ordered)
          case _ => s + n
        }
        case (_: Unordered) => (s find (x => x.id == ID('∀) && x.isInstanceOf[Unordered])) match {
          case Some(o: AllConstituent) => (s - o) + (new AllConstituent(o.but ++ n.but) with Required with Unordered)
          case _ => s + n
        }
        case (_: Limit) => (s find (x => x.id == ID('∀) && x.isInstanceOf[Limit])) match {
          case Some(o: AllConstituent) => (s - o) + (new AllConstituent(o.but ++ n.but) with Limit)
          case _ => s + n
        }
      }
      case x => s + x
    })
  )
    
  //TODO implement
  lazy val `extends` = "extends" ~> rep1sep(name, ",")
  
  lazy val element = ("element" ~> ident) ~ ("{" ~> opt(alternatives) <~ "}") ^^ {
    case id ~ Some(as) => new Elm(Symbol(id), as.reverse)
    case id ~ None     => new Elm(Symbol(id))
  }

  lazy val glblmt = 
    ( ("limit" ~ "{") ~> rep1sep(conselem, ",") <~ "}" ^^ {
      // missing combination AllConstituent is prevented by conselem
      case cs => Top(List(Alternative(constituents = ((Set[AbstractConstituent]() /: cs)((s, e) => (e: @unchecked) match {
        case Constituent(id)       => s + {new Constituent(id) with Limit}
        case TupleConstituent(id)  => s + {new TupleConstituent(id) with Limit}
        case TextConstituent()     => s + {new TextConstituent with Limit}
      })))))
    }
    | ("limit" ~ "{") ~> consallbut <~ "}" ^^ {case AllConstituent(not) => Top(List(Alternative(constituents = Set(new AllConstituent(not) with Limit))))}
    )

  lazy val alternatives =
    ( ("alternatives" ~ "{") ~> rep1("{" ~> altentry <~ "}") <~ "}" ^^ {case as => (List[Alternative]() /: as)((l, a) => (new Alternative(a._1, a._2)) :: l)}
    | altentry                                                      ^^ {case a  => List(Alternative(a._1, a._2))}
    )
  
  lazy val altentry =
    ( annotations ~ opt(constituents) ^^ {
      case as ~ Some(cs) => (as, cs)
      case as ~ None     => (as, Set.empty[AbstractConstituent])
    }
    | constituents ~ opt(annotations) ^^ {
      case cs ~ Some(as) => (as, cs)
      case cs ~ None     => (Set.empty[AbstractAnnotation], cs)
    }
    )
    
  lazy val annotations = ("annotations" ~ "{") ~> repsep((annoallbut | annoentry), ",") <~ "}" ^^ {case as => (Set[AbstractAnnotation]() /: as)(_ ++ _)}
  
  lazy val annoallbut: Parser[Set[AllAnnotation]] = "_" ~ opt(("\\" ~ "{") ~> rep1sep(ident, ",") <~ "}") ^^ {
    case all ~ Some(but) => Set(new AllAnnotation((but map (a => Symbol(a))).toSet) with Required)
    case all ~ None      => Set(new AllAnnotation with Required)
  }
    
  lazy val annoentry: Parser[Set[AbstractAnnotation]] =
    ( ident ~ opt("?") ~ rep("," ~> annoentry) ^^ {
      case id ~ Some(_) ~ as => (Set[AbstractAnnotation](new Annotation(Symbol(id)) with Optional) /: as)(_ ++ _)
      case id ~ None ~ as    => (Set[AbstractAnnotation](new Annotation(Symbol(id)) with Required) /: as)(_ ++ _)
    }
    | annoabsent ~ rep("," ~> annoentry) ^^ {case abs ~ as => (abs /: as)(_ ++ _)}
    )  
  
  lazy val annoabsent: Parser[Set[AbstractAnnotation]] = ("absent" ~ "{") ~> rep1sep(ident, ",") <~ "}" ^^ {
    case as => (as map (a => new Annotation(Symbol(a)) with Absent)).toSet
  }
  
  lazy val constituents = ("constituents" ~ "{") ~> opt(consentry) <~ "}" ^^ {
    case Some(cs) => cs
    case None     => Set.empty[AbstractConstituent]
  }
  
  lazy val consentry: Parser[Set[AbstractConstituent]] =
    ( consabsent ~ rep("," ~> consentry) ^^ {case abs ~ cs => (abs /: cs)(_ ++ _)}
    | ( "unordered" | "ordered" ) ~ conscoll ~ rep("," ~> consentry) ^^ {
      case "unordered" ~ coll ~ cs => (((Set[AbstractConstituent]() /: coll)((s, e) => e match {
        case AllConstituent(but) => s + {new AllConstituent(but) with Required with Unordered}
        case c: Constituent => c match {
          case _: Optional => s + {new Constituent(c.id) with Optional with Unordered}
          case _           => s + {new Constituent(c.id) with Required with Unordered}
        } 
        case t: TupleConstituent => t match {
          case _: Optional => s + {new TupleConstituent(t.id) with Optional with Unordered}
          case _           => s + {new TupleConstituent(t.id) with Required with Unordered}  
        }
        case x: TextConstituent => x match {
          case _: Optional => s + {new TextConstituent with Optional with Unordered}
          case _           => s + {new TextConstituent with Required with Unordered}  
        }        
      })) /: cs)(_ ++ _)
      case "ordered" ~ coll ~ cs   => (((Set[AbstractConstituent]() /: coll)((s, e) => e match {
        case AllConstituent(but) => s + {new AllConstituent(but) with Required with Ordered}
        case c: Constituent => c match {
          case _: Optional => s + {new Constituent(c.id) with Optional with Ordered}
          case _           => s + {new Constituent(c.id) with Required with Ordered}
        }
        case t: TupleConstituent => t match {
          case _: Optional => s + {new TupleConstituent(t.id) with Optional with Ordered}
          case _           => s + {new TupleConstituent(t.id) with Required with Ordered}
        }
        case x: TextConstituent => x match {
          case _: Optional => s + {new TextConstituent with Optional with Ordered}
          case _           => s + {new TextConstituent with Required with Ordered}
        }
      })) /: cs)(_ ++ _)
    }
    | loclmt ~ rep("," ~> consentry) ^^ {case l ~ cs => (l /: cs)(_ ++ _)}
    )
    
  lazy val consabsent = ("absent" ~ "{") ~> rep1sep(conselem, ",") <~ "}" ^^ {
    // missing combination AllConstituent is prevented by conselem
    case cs => (Set[AbstractConstituent]() /: cs)((s, e) => (e: @unchecked) match {
      case Constituent(id)       => s + {new Constituent(id) with Absent}
      case TupleConstituent(id)  => s + {new TupleConstituent(id) with Absent}
      case TextConstituent()     => s + {new TextConstituent with Absent}
    })
  }
  
  lazy val conscoll = {
    def a2t(a: AllConstituent) = (a, None)
    def p2t(p: ~[AbstractConstituent, Option[String]]) = p match {case c ~ o => (c, o)}
    
    lazy val elems = consallbut ^^ {a2t(_)} | (conselem ~ opt("?")) ^^ {p2t(_)}

    ( "{" ~> rep1sep(elems, ",") <~ "}" ^^ {
      // missing combination (AllConstituent, Some(_)) is prevented by a2t
      case cs => (Set[AbstractConstituent]() /: cs)((s, e) => (e: @unchecked) match {
        case (Constituent(id), Some(_))      => s + {new Constituent(id) with Optional}
        case (TupleConstituent(id), Some(_)) => s + {new TupleConstituent(id) with Optional}
        case (TextConstituent(), Some(_))    => s + {new TextConstituent with Optional}
        case (e, None)                       => s + e
      })
    }
    | "{" ~> rep1sep((conselem ~ opt("?")), ",") <~ "}" ^^ {
      // missing combination (AllConstituent, Some(_)) is prevented by conselem
      case cs => (Set[AbstractConstituent]() /: cs)((s, e) => (e: @unchecked) match {
        case Constituent(id) ~ Some(_)       => s + {new Constituent(id) with Optional}
        case TupleConstituent(id) ~ Some(_)  => s + {new TupleConstituent(id) with Optional}
        case TextConstituent() ~ Some(_)     => s + {new TextConstituent with Optional}
        case e ~ None                        => s + e
      })
    }
    )
  }
  
  lazy val loclmt = ("limit" ~ "{") ~> ((consallbut | conselem) ~ rep("," ~> (consallbut | conselem))) <~ "}" ^^ { 
    case h ~ t => (Set[AbstractConstituent]() /: (h :: t))((s, e) => e match {
      case AllConstituent(not)  => s + {new AllConstituent(not) with Limit}
      case Constituent(id)      => s + {new Constituent(id) with Limit}
      case TupleConstituent(id) => s + {new TupleConstituent(id) with Limit}
      case TextConstituent()    => s + {new TextConstituent with Limit}
    })
  }
    
  lazy val conselem: Parser[AbstractConstituent] = 
    ( ident                                ^^ {case id => new Constituent(ID(Symbol(id))) with Required}
    | "<TEXT>"                            ^^^ {new TextConstituent with Required}
    | "(" ~> rep1sep(conselem, ",") <~ ")" ^^ {case cs => new TupleConstituent(TupleID(cs map (_.id))) with Required}
    )
    
  lazy val consallbut: Parser[AllConstituent] = "_" ~ opt(("\\" ~ "{") ~> rep1sep(conselem, ",") <~ "}") ^^ {
    case all ~ Some(but) => new AllConstituent((but map (_.id)).toSet) with Required
    case all ~ None      => new AllConstituent with Required
  }

  lazy val name = ident ^^ {case id => Symbol(id)} | string ^^ {case id => Symbol(id)}
  
  lazy val string = accept("string", {case lexical.StringLit(n) => n})
}

// TOKENS ------------------------------------------------------------------------------------------

import scala.util.parsing.combinator._
import scala.util.parsing.combinator.lexical._
import scala.util.parsing.input.CharArrayReader.EofCh

private [math] class Lexer extends StdLexical with RegexParsers {
  override type Elem = Char

  override def token =
    ( string ^^ StringLit
    | number ^^ NumericLit
    | delim
    | EofCh ^^^ EOF
    | id ^^ { case i if reserved contains i => Keyword(i) case i => Identifier(i) }
    | '\"' ~> failure("Unterminated string")
    | failure("Illegal character")
    )

  lazy val string =
    ( '\"' ~> rep(charSeq | chrExcept('\"', '\n', EofCh)) <~ '\"' ^^ { _ mkString "" }
    | '\'' ~> rep(charSeq | chrExcept('\'', '\n', EofCh)) <~ '\'' ^^ { _ mkString "" }
    )
    
  lazy val charSeq =
    ( '\\' ~ '\"' ^^^ "\""
    | '\\' ~ '\\' ^^^ "\\"
    | '\\' ~ '/' ^^^ "/"
    | '\\' ~ 'b' ^^^ "\b"
    | '\\' ~ 'f' ^^^ "\f"
    | '\\' ~ 'n' ^^^ "\n"
    | '\\' ~ 'r' ^^^ "\r"
    | '\\' ~ 't' ^^^ "\t"
    | '\\' ~ 'u' ~> unicodeBlock
    )

  lazy val number = """-?(\d+(\.\d*)?|\d*\.\d+)([eE][+-]?\d+)?[fFdD]?""".r

  lazy val id =
    ( '?' ^^^ "?"
    | rep( letter
       | digit
       | elem("underscore", _ == '_')
       | elem("hyphen", _ == '-')
       //| elem("questionmark", _ == '?')
       | elem("backslash", _ == '\\')
       | elem("lbracket", _ == '<')
       | elem("rbracket", _ == '>')
       ) ^^ { _ mkString "" }
    )

  import scala.io.UTF8Codec.{ encode }
  lazy val unicodeBlock = hexDigit ~ hexDigit ~ hexDigit ~ hexDigit ^^ {
    case a ~ b ~ c ~ d => new String(Array(Integer.parseInt(List(a, b, c, d) mkString "", 16)), 0, 1).getBytes("UTF-8")
  }

  lazy val hexDigits = Set[Char]() ++ "0123456789abcdefABCDEF".toArray

  lazy val hexDigit = elem("hex digit", hexDigits.contains(_))
}
